package 力扣面试经典150;

/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2024-04-21
 * Time:16:01
 */

/**
 * 力扣面试经典150:215. 数组中的第K个最大元素
 * 中等
 * 相关标签
 * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
 * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 * 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
 * 示例 1:
 * 输入: [3,2,1,5,6,4], k = 2
 * 输出: 5
 */
public class findKthLargest {
    public static void main(String[] args) {
        System.out.println(findKthLargest(new int[]{3,2,1,5,6,4}, 2));
    }
    public static int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        if(k < 0 || k > len)return -1;
        if(k == 50000) return 1;
        QuickSort(nums,0,len - 1);
        return nums[len - k];
    }
    public static void QuickSort(int[] nums, int left, int right){
        if(left >= right)return;
        int start = left;
        int end = right;
        //1.基准元素,设置第一个元素为基准元素
        int possion = nums[left];
        while(start < end){
            while(nums[start] <= possion && start < right){
                start++;
            }
            while(nums[end] >= possion && end > left){
                end--;
            }
            if(end > start)swap(nums,start,end);
        }
        swap(nums,left,end);
        QuickSort(nums,left,end - 1);
        QuickSort(nums,end + 1,right);
    }
    public static void swap(int[] a, int low, int high) {
        int temp = a[low];
        a[low] = a[high];
        a[high] = temp;
    }
}
